#pragma once
#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<string>
using namespace std;
namespace hash_bucket
{

	template<class T>
	struct DefaultHashFunc
	{
		size_t operator()(const T& _data)
		{
			return (size_t)_data;
		}
	};
	template<>
	struct DefaultHashFunc<string>
	{
		size_t operator()(const string& str)
		{
			size_t hash = 0;
			for (auto ch : str)
			{
				hash *= 131;
				hash += ch;
			}

			return hash;
		}
	};
	template<class T>
	struct Hash_Data
	{
		T kv;
		Hash_Data* next;
		Hash_Data(const T& _kv) :kv(_kv), next(nullptr)
		{}
	};

	template<class K, class T, class KeyOfT, class HashFunc>
	class Hash_Table;

	template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
	struct HTIterator
	{
		typedef Hash_Data<T> Node;
		typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
		typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;
		HTIterator(Node* _node,const Hash_Table<K, T, KeyOfT,HashFunc>* _table):node(_node),table(_table)
		{}
		HTIterator(const Iterator& it):node(it.node),table(it.table)
		{}
		Ref operator*()
		{
			return node->kv;
		}
		Ptr operator->()
		{
			return &(node->kv);
		}
		Self operator++()
		{
			if (node->next)
			{
				node = node->next;
				return *this;
			}
			else
			{
				HashFunc hs;
				KeyOfT kot;
				size_t _data = hs(kot(node->kv)) % (table->_table.size());
				_data++;
				while (_data < (table->_table.size()))
				{
					if (table->_table[_data])
					{
						node = table->_table[_data];
						return *this;
					}
					else
					{
						_data++;
					}
				}
				node = nullptr;
				return *this;
			}
		}
		bool operator!=(const Self& s)
		{
			return node != s.node;
		}
		bool operator==(const Self& s)
		{
			return node == s.node;
		}
		Node* node;
		const Hash_Table<K, T, KeyOfT,HashFunc>* table;
	};


	template<class K, class T,class KeyofT, class Hashfunc = DefaultHashFunc<K>>
	class Hash_Table
	{
		template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
		friend struct HTIterator;
	public:
		typedef Hash_Data<T> Node;
		typedef HTIterator<K, T, T*, T&, KeyofT, Hashfunc> iterator;
		typedef HTIterator<K, T, const T*, const T&, KeyofT,Hashfunc> const_iterator;
		Hashfunc hs;
		KeyofT kot;

		Hash_Table()
		{
			_table.resize(10, nullptr);
		}
		~Hash_Table()
		{
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->next;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
		}
		iterator begin()
		{
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				if (cur)
				{
					return iterator(cur, this);
				}
			}
			return iterator(nullptr, this);
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}
		const_iterator begin()const
		{
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				if (cur)
				{
					return iterator(cur, this);
				}
			}
			return iterator(nullptr, this);
		}
		const_iterator end()const
		{
			return iterator(nullptr, this);
		}
		template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
		friend struct HTIterator;
		iterator Find(const K& data)
		{
			size_t _data = hs(data) % _table.size();
			Node* cur = _table[_data];
			while (cur)
			{
				if (kot(cur->kv) == data)
				{
					return 	iterator(cur,this);
				}
				cur = cur->next;
			}
			return iterator(nullptr,this);
		}
		pair<iterator, bool> Insert(const T& _kv)
		{
			iterator it = Find(kot(_kv));
			if (it!=end())
			{
				return make_pair(it, false);
			}
			if (_n / _table.size() == 1)
			{
				Hash_Table newtable;
				newtable._table.resize(2 * _table.size());
				for (int i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						newtable.Insert(cur->kv);
						cur = cur->next;
					}
					_table[i] = nullptr;
				}
				swap(newtable._table, _table);
			}
			size_t _data = hs(kot(_kv)) % _table.size();
			Node* node = new Node(_kv);
			node->kv = _kv;
			node->next = _table[_data];
			_table[_data] = node;
			_n++;
			return make_pair(iterator(node, this), true);
		}
		bool Erase(const K& key)
		{
			size_t _data = hs(key) % _table.size();
			Node* cur = _table[_data];
			while (cur)
			{
				if (hot(cur->kv) == key)
				{
					break;
				}
				cur = cur->next;
			}
			if (cur == nullptr)
				return false;
			Node* ptr = _table[_data];
			if (ptr == cur)
			{
				_table[_data] = ptr->next;
				delete ptr;
				return true;
			}
			while (1)
			{
				if (ptr->next == cur)
				{
					break;
				}
				ptr = ptr->next;
			}
			ptr->next = ptr->next->next;
			cur->next = nullptr;
			delete cur;
			return true;
		}
		void Print()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				printf("[%d]->", i);
				Node* cur = _table[i];
				while (cur)
				{
					cout << cur->kv.first << ":" << cur->kv.second << "->";
					cur = cur->next;
				}
				printf("NULL\n");
			}
			cout << endl;
		}
	private:
		size_t _n = 0;
		vector<Node*> _table;
	};
};